package com.asia.algorithmcode.binaryTree;

import java.util.*;

/**
 * @DESCRIPTION: 103、二叉树的锯齿形层序遍历
 * @USER: wanfu
 * @DATE: 2025/5/9 星期五 14:26
 */
public class ZigzagLevelOrder {


    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2_1 = new TreeNode(2);
        TreeNode n2_2 = new TreeNode(3);
        TreeNode n3_1 = new TreeNode(4);
        TreeNode n3_2 = new TreeNode(5);
        TreeNode n4_1 = new TreeNode(6);
        TreeNode n4_2 = new TreeNode(7);

        n1.left = n2_1;
        n1.right = n2_2;
        n2_1.left = n3_1;
        n2_1.right = n4_1;
        n2_2.left = n4_2;
        n2_2.right = n3_2;

        List<List<Integer>> lists = new ZigzagLevelOrder().zigzagLevelOrder(n1);

        System.out.println(" ");
    }

    List<List<Integer>> list = new ArrayList<>();

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Deque<TreeNode> arr = new LinkedList<>();
        arr.push(root);
        boolean flag = false;
        while (!arr.isEmpty()) {
            Deque<Integer> innerList = new ArrayDeque<>();
            int n = arr.size();
            for (int i = 0; i < n; i++) {
                TreeNode pop = arr.poll();
                if (flag) {
                    innerList.offerFirst(pop.val);
                } else {
                    innerList.offerLast(pop.val);
                }

                if (pop.left != null) {
                    arr.add(pop.left);
                }
                if (pop.right != null) {
                    arr.add(pop.right);
                }
            }
            list.add(new LinkedList<>(innerList));
            flag = !flag;
        }
        return list;
    }

}
